#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "psm.h"
#include "rINDIE.h"


rINDIEHypothesis::rINDIEHypothesis(rINDIEHypothesis *h)
{
	m_patterns.Copy(h->m_patterns);
	m_solutions.Copy(h->m_solutions);
	m_reliability.Copy(h->m_reliability);
	m_default_solution=new FeatureTerm(h->m_default_solution);
} /* rINDIEHypothesis::rINDIEHypothesis */ 


bool rINDIEHypothesis::learn(List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic)
{
	FeatureTerm *solution;
	List<FeatureTerm> solutions;
	List< List<FeatureTerm> > descriptions;
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;


	/* Compute the different solutions: */ 
	{
		int pos;
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;
			
			pos=solutions.Position(s);
			if (pos==-1) {
				solutions.Add(s);
				tmp=new List<FeatureTerm>;
				tmp->Add(d);
				descriptions.Add(tmp);
			} else {
				delete s;
				descriptions[pos]->Add(d);
			} /* if */ 
		} /* while */ 
	}

	/* Compute the default solution: */ 
	{
		int max=-1;
		FeatureTerm *s;
		List<FeatureTerm> *tmp;

		m_default_solution=0;

		solutions.Rewind();
		descriptions.Rewind();

		while(solutions.Iterate(s) &&  descriptions.Iterate(tmp)) {
			if (max==-1 || tmp->Length()>max) {
				max=tmp->Length();
				delete m_default_solution;
				m_default_solution=new FeatureTerm(s);
			} /* if */ 
		} /* while */ 
	}

	solutions.Rewind();
	while(solutions.Iterate(solution)) {
		/* Learn a set of patterns for the current solution: */ 
		{
			char *s=solution->toStringNOOS(domain_model);
			printf("\nrINDIE: building model for %s --------------------------------------------------\n\n",s);
			delete []s;
		}

		/* Create the positive and negative examples lists: */ 
		{
			FeatureTerm *sol,*des;
			List<FeatureTerm> l1,*tmp;
			List< List<FeatureTerm> > l2;

			l1.Instance(solutions);
			l2.Instance(descriptions);
			while(l1.Iterate(sol) && l2.Iterate(tmp)) {
				if (*sol==*solution) {
					tmp->Rewind();
					while(tmp->Iterate(des)) positive.Add(des);
				} else {
					tmp->Rewind();
					while(tmp->Iterate(des)) negative.Add(des);
				} /* if */ 
			} /* while */ 
		}

		FeatureTerm *description;

		description=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);
		INDIE(description,solution,&positive,&negative,heuristic,o,domain_model);
		delete description;

		while(!positive.EmptyP()) positive.ExtractIni();
		while(!negative.EmptyP()) negative.ExtractIni();
	} /* while */ 

	return true;
} /* rINDIEHypothesis::learn */ 



bool rINDIEHypothesis::learn_single_class(FeatureTerm *solution,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic)
{
	List<FeatureTerm> solutions;
	List< List<FeatureTerm> > descriptions;
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;


	/* Compute the different solutions: */ 
	{
		int pos;
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;
			
			pos=solutions.Position(s);
			if (pos==-1) {
				solutions.Add(s);
				tmp=new List<FeatureTerm>;
				tmp->Add(d);
				descriptions.Add(tmp);
			} else {
				delete s;
				descriptions[pos]->Add(d);
			} /* if */ 
		} /* while */ 
	}

	/* Compute the default solution: */ 
	{
		int max=-1;
		FeatureTerm *s;
		List<FeatureTerm> *tmp;

		m_default_solution=0;

		solutions.Rewind();
		descriptions.Rewind();

		while(solutions.Iterate(s) &&  descriptions.Iterate(tmp)) {
			if (max==-1 || tmp->Length()>max) {
				max=tmp->Length();
				delete m_default_solution;
				m_default_solution=new FeatureTerm(s);
			} /* if */ 
		} /* while */ 
	}

	/* Learn a set of patterns for the current solution: */ 
	{
		char *s=solution->toStringNOOS(domain_model);
		printf("\nrINDIE: building model for %s --------------------------------------------------\n\n",s);
		delete []s;
	}

	/* Create the positive and negative examples lists: */ 
	{
		FeatureTerm *sol,*des;
		List<FeatureTerm> l1,*tmp;
		List< List<FeatureTerm> > l2;

		l1.Instance(solutions);
		l2.Instance(descriptions);
		while(l1.Iterate(sol) && l2.Iterate(tmp)) {
			if (*sol==*solution) {
				tmp->Rewind();
				while(tmp->Iterate(des)) positive.Add(des);
			} else {
				tmp->Rewind();
				while(tmp->Iterate(des)) negative.Add(des);
			} /* if */ 
		} /* while */ 
	}

	FeatureTerm *description;

	description=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);
	INDIE(description,solution,&positive,&negative,heuristic,o,domain_model);
	delete description;

	while(!positive.EmptyP()) positive.ExtractIni();
	while(!negative.EmptyP()) negative.ExtractIni();

	return true;
} /* rINDIEHypothesis:learn_single_class */ 


void rINDIEHypothesis::INDIE(FeatureTerm *description,FeatureTerm *solution,List<FeatureTerm> *positive,List<FeatureTerm> *negative,int heuristic,Ontology *o,FTKBase *domain_model)
{
	List<FeatureTerm> initial_l;
	List<FeatureTerm> au_l;
	FeatureTerm *au;
	List<FeatureTerm> negative_covered,negative_uncovered;
	List<FeatureTerm> positive_covered,positive_uncovered;

	initial_l.Add(new FeatureTerm(description));

	printf("rINDIE: computing antiunification with %i objects...\n",positive->Length());
	antiunification(&au_l,positive,SPECIALIZATION_LANGUAGE_L2,&initial_l,o,domain_model,true,AU_VERSION_FAST);
	au=au_l.ExtractIni();
	if (au!=0) {
		List<FeatureTerm> l;
		FeatureTerm *example;

/*
		{
			char *s;
			printf("Antiunification:\n");
			s=au->toStringNOOS(domain_model);
			printf("%s\n",s);
			delete []s;
		}
*/
		l.Instance(*negative);
		l.Rewind();
		while(l.Iterate(example)) {
			if (au->subsumes(example)) {
				negative_covered.Add(example);
			} else {
				negative_uncovered.Add(example);
			} /* if */ 
		} /* while */ 

		if (negative_covered.EmptyP()) {
			/* Rule found!!! */ 
			{
				FeatureTerm *f;
				f=au;
				au=generalize_pattern(au,positive,negative,o,domain_model);
				delete f;
				m_patterns.Add(au);
			}
			m_solutions.Add(new FeatureTerm(solution));
			m_reliability.Add(new float(1));

			printf("rINDIE: new rule found , covers %i positive examples and 0 negative examples\n",positive->Length());
			{
				char *s1,*s2;
				s1=solution->toStringNOOS(domain_model);
				s2=au->toStringNOOS(domain_model);
				printf("rINDIE: rule is for class %s,\n%s\n\n",s1,s2);
				delete []s1;
				delete []s2;
			}					
		} else {
			/* Rule is too general, the space of problems has to be partitioned: */ 
			List<FeatureTerm> *refinements;
			FeatureTerm *refinement;
			int selected,nrefinements;
			float *heuristics;
			int i;

			refinements = DSpecializationL2_b(au,positive,0,o,domain_model);

			/* Choose one refinement according to the heuristic: */ 

			/* Filter refinements: */ 
			{
				List<FeatureTerm> to_delete;

				refinements->Rewind();
				while(refinements->Iterate(refinement)) {
					if (refinement->subsumes(au)) to_delete.Add(refinement);
				} /* while */ 

				while(!to_delete.EmptyP()) {
					refinement=to_delete.ExtractIni();
					refinements->DeleteElement(refinement);
					delete refinement;
				} /* while */ 
			}

//			printf("%i refinements\n",refinements->Length());
		
			selected=-1;
			if (refinements->Length()>0) {

				/* Evaluate all the refinements: */ 
				nrefinements=refinements->Length();
				heuristics=new float[nrefinements];
//				printf("Heuristics:\n");
				i=0;
				refinements->Rewind();
				while(refinements->Iterate(refinement)) {
					switch(heuristic) {
					case 0:	/* Information Gain: */ 
							{
								int before_p=0,before_n=0,before=0;
								int after_p=0,after_n=0,after=0;
								float before_i,after_i1,after_i2;
								FeatureTerm *f;
								double LOG2E=log(2.0);

								before=positive->Length()+negative->Length();
								positive->Rewind();
								while(positive->Iterate(f)) {
									if (au->subsumes(f)) before_p++;
									if (refinement->subsumes(f)) after_p++;
								} /* if */ 
								negative->Rewind();
								while(negative->Iterate(f)) {
									if (au->subsumes(f)) before_n++;
									if (refinement->subsumes(f)) after_n++;
								} /* if */ 

								after=after_p+after_n;

								before_i=float(-(log(float(before_p)/float(before_p+before_n))/LOG2E));
								if (after==0) {
									after_i1=0;
								} else {
									if (after_p==0) {
										after_i1=1;
									} else {
										after_i1=float(-(log(float(after_p)/float(after))/LOG2E));
									} /* if */ 
								} /* if */ 
								if (before-after==0) after_i2=0;
										 	    else after_i2=float(-(log(float(before_p-after_p)/float(before-after))/LOG2E));

								heuristics[i]=-(before_i-(after*after_i1+(before-after)*after_i2)/before);
//								printf("%g {%g,%g} [%i,%i] -> [%i,%i]/[%i,%i] (%i -> %i)\n",heuristics[i],after_i1,after_i2,before_p,before_n,after_p,after_n,before_p-after_p,before_n-after_n,before,after);
							}
							break;
					case 1: /* RLDM: */ 
							heuristics[i]=0;
							break;
					default:heuristics[i]=0;
							break;
					} /* switch */ 
						

					i++;
				} /* while */ 

				/* Choose one refinement: */ 
				{
					int i;
					float maximum=heuristics[0];
					selected=0;

					for(i=1;i<nrefinements;i++) {
						if (heuristics[i]>maximum) {
							maximum=heuristics[i];
							selected=i;
						} /* if */ 
					} /* for */  
				}

//				printf("Refinement selected: %i\n",selected);
				refinement=refinements->operator [](selected);

				l.Instance(*positive);
				l.Rewind();
				while(l.Iterate(example)) {
					if (refinement->subsumes(example)) {
						positive_covered.Add(example);
					} else {
						positive_uncovered.Add(example);
					} /* if */ 
				} /* while */ 

//				printf("(%i - %g) %i covered, %i uncovered\n",selected,heuristics[selected],positive_covered.Length(),positive_uncovered.Length());

				if (!positive_covered.EmptyP()) INDIE(refinement,solution,&positive_covered,negative,heuristic,o,domain_model);
				if (!positive_uncovered.EmptyP() && positive_uncovered.Length()<positive->Length()) {
					negative->Add(refinement);
					INDIE(description,solution,&positive_uncovered,negative,heuristic,o,domain_model);
					negative->DeleteElement(refinement);
				} /* if */ 

				delete []heuristics;
			} /* if */ 
	
			delete refinements;
			delete au;

		} /* if */ 
	} else {
		printf("rINDIE: error computing antiunification!\n");
	} /* if */ 

	while(!negative_covered.EmptyP()) negative_covered.ExtractIni();
	while(!negative_uncovered.EmptyP()) negative_uncovered.ExtractIni();
	while(!positive_covered.EmptyP()) positive_covered.ExtractIni();
	while(!positive_uncovered.EmptyP()) positive_uncovered.ExtractIni();

} /* rINDIEHypothesis::INDIE */ 


FeatureTerm *rINDIEHypothesis::generalize_pattern(FeatureTerm *pattern,List<FeatureTerm> *positive,List<FeatureTerm> *negative,Ontology *o,FTKBase *domain_model)
{
	List<FeatureTerm> l3;
	List<FeatureTerm> *l;
	FeatureTerm *f,*f2,*d;
	bool end,c1,c2;

	f=new FeatureTerm(pattern);

	do{
		end=true;
		l=DGeneralization(f,o,domain_model);

		l->Rewind();
		while(l->Iterate(f2) && end) {
/*
			{
				char *s;
				s=f2->toStringNOOS(domain_model);
				printf("Considering: \n%s\n",s);
				delete []s;
			}
*/			
			c1=true;
			l3.Instance(*positive);
			l3.Rewind();
			while(l3.Iterate(d) && c1) {
				if (!f2->subsumes(d)) {
					c1=false;
/*
					{
						char *s;
						s=d->toStringNOOS(domain_model);
						printf("Does not subsume: \n%s\n",s);
						delete []s;
					}
*/
				} /* if */ 
			} /* while */ 

			c2=true;
			l3.Instance(*negative);
			l3.Rewind();
			while(l3.Iterate(d) && c2) {
				if (f2->subsumes(d)) c2=false;
			} /* while */ 

			if (c1 && c2) {
//				printf("Ok\n");
				delete f;
				f=new FeatureTerm(f2);
				end=false;
			} else {
//				printf("Fail %s %s\n",(c1 ? "true":"false"),(c2 ? "true":"false"));
			} /* if */ 
		} /* if */ 
		delete l;
	}while(!end);
/*
	{
		char *s;
		s=f->toStringNOOS(domain_model);
		printf("Generalized pattern: \n%s\n",s);
		delete []s;
	}
*/
	return f;
} /* rINDIEHypothesis::generalize_pattern */ 

